package com.zjj.lbw.interview.array;

import java.util.Arrays;

/**
 * @author zhanglei.zjj
 * @description 合并两个有序数组
 *  两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
 *  初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。假设 nums1 的空间大小等于 m + n，这样它就 有足够的空间保存来自 nums2 的元素。
 * @date 2023/9/2 16:45
 */
public class MergeSortedArray {
    /**
     * 基于jdk中的复制、排序
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public static void merge1(int[] nums1, int m, int[] nums2, int n) {
        System.arraycopy(nums2, 0, nums1, m, n);
        Arrays.sort(nums1);
    }

    /**
     * 双指针，从前往后移动
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public static void merge2(int[] nums1, int m, int[] nums2, int n) {
        int[] nums1_copy = new int[m];
        // 因为题目最后要求，是nums1 最后是一个有序数组，它才是存储最终排序结果的载体
        System.arraycopy(nums1, 0, nums1_copy, 0, m);

        // p1指针指向nums1_copy, p2指向nums2，p指向 nums1
        int p1 = 0, p2 = 0, p = 0;
        while (p1 < m && p2 < n) {
            nums1[p++] = nums1_copy[p1] < nums2[p2] ? nums1_copy[p1++] : nums2[p2++];
        }

        // p1还没有移动完，p2已经移动完
        if (p1 < m) {
            System.arraycopy(nums1_copy, p1, nums1, p1 + p2, m + n - p1 - p2);
        }

        // p1已经移动完，p2还没有移动完
        if (p2 < n) {
            System.arraycopy(nums2, p2, nums1, p1 + p2, m + n - p1 - p2);
        }
    }

    /**
     * 双指针-从后往前移动
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public static void merge3(int[] nums1, int m, int[] nums2, int n) {
        // p1指针指向nums1_copy, p2指向nums2，p指向 nums1
        int p1 = m - 1, p2 = n - 1, p = m + n - 1;
        while (p1 >= 0 && p2 >= 0) {
            nums1[p--] = nums1[p1] > nums2[p2] ? nums1[p1--] : nums2[p2--];
        }
        //  如果p2都移动完，p1本身就在nums1数组中，这种情况 肯定是有序的，不需要额外处理
        // 如果p2 还没移动完，这说明 nums1数组中有最小元素都比nums2数组中剩余元素大，这种情况需要将nums2数组中剩余元素拷贝回去
        if (p2 >= 0) {
            System.arraycopy(nums2, 0, nums1, 0, p2 + 1);
        }
    }
}
